package com.mj.listen2._01_排序.other;

import com.mj.listen2._01_排序.tools.Asserts;

/**
 * 二分查找，前提：数组必须有序
 */
public class BinarySearch {
    public static void main(String[] args) {
//        int[] arr = {1, 12, 18, 24, 25, 35, 39, 54, 78, 80, 99};
//        System.out.println(binarySearch(arr, 1));
//        System.out.println(binarySearch(arr, 99));
//        System.out.println(binarySearch(arr, 54));
        int[] arr = {2, 4, 8, 8, 8, 12, 14};
        Asserts.test(search(arr, 5) == 2);
        Asserts.test(search(arr, 1) == 0);
        Asserts.test(search(arr, 15) == 7);
        Asserts.test(search(arr, 8) == 5);
    }

    /**
     * 去有序数组中查找 value 对应的索引
     */
    private static int binarySearch(int[] arr, int value) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int begin = 0;
        // end指针指向数组索引最外一个。[0,end)  左闭右开
        int end = arr.length;
        while (begin < end) {
            int mid = ((end + begin) >> 1);
            if (value < arr[mid]) {
                // 往左边找
                end = mid;
            } else if (value > arr[mid]) {
                // 往右边找
                begin = mid + 1;
            } else {
                // 找到了
                return mid;
            }
        }
        return -1;
    }

    /**
     * 去有序数组中查找第一个大于 value 的索引
     */
    private static int search(int[] arr, int value) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int begin = 0;
        int end = arr.length;
        int mid;
        while (begin < end) {
            mid = (begin + end) >> 1;
            if (value < arr[mid]) {
                // 如果value < arr[mid]，去[begin,mid)范围去找
                end = mid;
            } else {
                // 如果value >= arr[mid]，去[mid+1,end)范围去找
                begin = mid + 1;
            }
        }
        return begin;
    }
}
